package com.springchang.algorithm.greedy;

import java.util.*;

/**
 * 贪心算法求解电台覆盖率问题
 * @author 张翠山
 * @date   20211003
 */
public class GreedyAlgorithm {

    public static void main(String[] args) {

        //定义一个hashmap存在电台以及覆盖率
        Map<String, Set<String>> broadCasts = new HashMap<String, Set<String>>();

        broadCasts.put("K1", new HashSet<>(Arrays.asList(new String[]{"北京", "上海", "天津"})));
        broadCasts.put("K2", new HashSet<>(Arrays.asList(new String[]{"广州", "北京", "深圳"})));
        broadCasts.put("K3", new HashSet<>(Arrays.asList(new String[]{"成都", "上海", "杭州"})));
        broadCasts.put("K4", new HashSet<>(Arrays.asList(new String[]{"上海", "天津"})));
        broadCasts.put("K5", new HashSet<>(Arrays.asList(new String[]{"杭州", "大连"})));

        //已经选择的电台
        Set<String> selects = new HashSet<>();
        //需要被覆盖的地区
        Set<String> toCoverAreas = new HashSet<>();

        //遍历broadCasts 取出所有的key和value
        for (String key :broadCasts.keySet()) {
            toCoverAreas.addAll(broadCasts.get(key));
        }

        //当需要被覆盖的地区未清空时，循环一直继续
        while(toCoverAreas.size() > 0) {
          String maxKey = null; //记录当前最优的key

          //遍历broadCasts 拿到当前key对应的value与需要覆盖地区的交集
            for (String key :broadCasts.keySet()) {
                //从电台map中取出当前电台能够覆盖的地区
                Set<String> broadCastSet = broadCasts.get(key);
                //当前覆盖地区与需要被覆盖地区取交集
                broadCastSet.retainAll(toCoverAreas);

                //体现贪心的代码，就是每次只取最优方案
                if(maxKey == null || broadCastSet.size() > broadCasts.get(maxKey).size()) {
                    //maxKey为空则表示第一次访问
                    maxKey = key;
                }
            }

            if(maxKey != null) {
                //向集合中添加当前最优解的电台
                selects.add(maxKey);
                //同时从需要被覆盖的地区集合中移除当前电台覆盖地区的集合
                toCoverAreas.removeAll(broadCasts.get(maxKey));
            }
        }
        System.out.println(selects);
    }
}
